const cheng = (a, b) => {
  // console.log(a, b);
  return {
    x: a.x * b.x - a.y * b.y,
    y: a.x * b.y + a.y * b.x,
  };
};

const jia = (a, b) => {
  return {
    x: a.x + b.x,
    y: a.y + b.y,
  };
};
const jian = (a, b) => {
  return {
    x: a.x - b.x,
    y: a.y - b.y,
  };
};

const FFT = (a, n, ty) => {
  for (var i = 0, j = 0; i < n; ++i) {
    if (i < j) {
      var tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
    }
    for (var k = n >> 1; (j ^= k) < k; k >>= 1);
  }

  for (var m = 2; m <= n; m <<= 1) {
    var w1 = {
      x: Math.cos((2 * Math.PI) / m),
      y: ty * Math.sin((2 * Math.PI) / m),
    };
    for (var i = 0; i < n; i += m) {
      var w = {
        x: 1,
        y: 0,
      };

      for (var k = 0; k < m >> 1; ++k) {
        // var t = { x: 0, y: 0 };

        // console.log(i + k + (m >> 1), w, a[i + k + (m >> 1)]);

        var t = cheng(w, a[i + k + (m >> 1)]);
        var u = a[i + k];
        a[i + k] = jia(u, t);
        a[i + k + (m >> 1)] = jian(u, t);
        w = cheng(w, w1);
      }
    }
  }
};

export const multiply = (a, b) => {
  var n = a.length - 1,
    m = b.length - 1;

  var tot = 1;

  for (var i in a) {
    if (a[i] == null) a[i] = 0;
  }
  for (var i in b) {
    if (b[i] == null) b[i] = 0;
  }

  while (tot <= n + m) tot += tot;

  var A = [],
    B = [];

  for (var i in a) {
    A.push({
      x: a[i],
      y: 0,
    });
  }

  for (var i = n + 1; i <= tot; ++i) {
    A[i] = {
      x: 0,
      y: 0,
    };
  }
  for (var i in b) {
    B.push({
      x: b[i],
      y: 0,
    });
  }
  for (var i = m + 1; i <= tot; ++i) {
    B[i] = {
      x: 0,
      y: 0,
    };
  }
  FFT(A, tot, 1);
  FFT(B, tot, 1);
  for (var i = 0; i <= tot; ++i) A[i] = cheng(A[i], B[i]);
  FFT(A, tot, -1);
  var ans = [];
  for (var i = 0; i <= n + m; ++i) {
    ans.push(Math.floor(A[i].x / tot + 0.5));
  }
  console.log(ans);
  return ans;
};
